#include "bitset.h"
//布隆过滤器是为了解决非整型的数据的海量搜索问题
class Hashfunc1
{
public:
    size_t operator()(const string& s)
    {
        size_t hash = 0;
        for (auto ch : s)
        {
            hash *= 131;
            hash += ch;
        }

        return hash;
    }
};
class Hashfunc2
{
public:
    size_t operator()(const string& s)
    {
        size_t hash = 0;
        for (size_t i = 0; i < s.size(); i++)
        {
            if ((i & 1) == 0) // 偶数位字符
            {
                hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
            }
            else              // 奇数位字符
            {
                hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));
            }
        }

        return hash;
    }
};
class Hashfunc3
{
public:
    size_t operator()(const string& s)
    {
        size_t hash = 5381;
        for (auto ch : s)
        {
            hash = hash * 33 ^ ch;
        }

        return hash;
    }
};
template <size_t N, class T = string,
          class Hashfunc1 = Hashfunc1,
          class Hashfunc2 = Hashfunc2,
          class Hashfunc3 = Hashfunc3>


class BHB
{
public:

    void set(const T& val)
    {
        _bs.test(Hashfunc1()(val) % M);
        _bs.test(Hashfunc2()(val) % M);
        _bs.test(Hashfunc3()(val) % M);
    }

    bool test(const T& val)
    {
        if(_bs.test(Hashfunc1()(val) % M)
        && _bs.test(Hashfunc2()(val) % M)
        && _bs.test(Hashfunc3()(val)) % M)
            return true;
        return false;
    }
private:
    static const size_t M = N * 4;
    wyd::bitset<M> _bs;
};